package ACwing.P4Math.Combinatorial_Number;

import java.io.*;

/**
 * @Date : 2023-03-24
 * @Description:887. 求组合数 III
 * C62=6x5/2x1
 * Cab=Ca-1 b +Ca-1 b-1
 * 询问次数少，但是数据范围巨大   卢卡斯定理
 *(1+x)^(p^k)mod p=（Cp0 1+cp1 x + cp2 x2 +……  中间的每一项Mod p 为0）同余  1+x^(p^k) mod p
 * Cab同余 {(C amod p  bmod p ) x ( C a/p  b/p) } mod p
 * O(logp N x P x logp
 */
public class CN03 {
    static BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
    static int n,p;
    static int N=2010;
    static int [][]c=new int[N][N];//预处理组合数所有的情况

    public static void main(String[] args) throws IOException {
        n=Integer.parseInt(br.readLine());
        long a,b;
        int p;
        while (n--!=0){
            String[] strings = br.readLine().split("\\s+");
            a=Long.parseLong(strings[0]);
            b=Long.parseLong(strings[1]);
            p=Integer.parseInt(strings[2]);
            bw.write(String.valueOf(lucas(a,b)));
            bw.newLine();
        }
        bw.flush();
    }
    static long lucas(long a,long b){
        if(a<p && b<p) return C(a,b);
        return C(a%p,b%p)*lucas(a/p,b/p)%p;
    }
    static long C(long a,long b){
        long res=1;
        int i,j;
        for (i = 1,j= (int) a; i <=b ; i++ ,j--) {
            res=res*j%p;
            res=res*qmi(i,p-2)%p;
        }
        return res;
    }
    static long qmi(int a,int b ){
        long res=1;
        while (b!=0){
            if((b&1)==1) res=res*a%p;
            a=a*a%p;
            b>>=1;
        }
        return res;
    }
}
